package _17_剑指Offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _57_剑指OfferII和为s的连续正数序列 {

    public static void main(String[] args) {

        _57_剑指OfferII和为s的连续正数序列 v = new _57_剑指OfferII和为s的连续正数序列();

        System.out.println(Arrays.deepToString(v.findContinuousSequence(9)));

    }

    // 根据等差数列求和公式
    public int[][] findContinuousSequence(int target) {
        List<int[]> results = new ArrayList<>();
        int left = 1;
        int right = 1;
        int sum = 1;
        while (left <= right) {
            while (sum <= target) {
                if (sum == target) {
                    int[] temp = new int[right - left + 1];
                    for (int i = left; i <= right; i++) {
                        temp[i - left] = i;
                    }
                    results.add(temp);
                }
                sum += ++right;
            }
            // 小于
            while (left <= right && sum >= target) {
                if (sum == target && right - left > 0) {
                    int[] temp = new int[right - left + 1];
                    for (int i = left; i <= right; i++) {
                        temp[i - left] = i;
                    }
                    results.add(temp);
                }
                sum -= left++;
            }
        }
        return results.toArray(new int[0][]);
    }

}
